/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package lab9;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

/**
 *
 * @author yashraj
 */
public class DijkstraAlgorithm 
{
    private int output1, set_of_roads, no_of_cities, temp_road_toll = 0, max_value = 0;
    private String cities, toll_table, min_toll, delims, delim, start_city, end_city;
    private int temp_start_city = 0, temp_end_city = 0, start_city_id = 0, end_city_id = 0, x = 0, temp_start = 0, t=0;
    private int[][] adj_matrix, temp_adj_matrix, temp_final_matrix, final_matrix;
    private HashMap<Integer, Integer> hm_visited;
    private HashMap<Integer, String> hm_city;
    private ArrayList<String> al_start_city, al_end_city, al_cities, al_tk_toll_table, al_tk_min_toll;
    private ArrayList<Integer> al_toll, al_next, al_cost, al_next_nodes, al_temp, al_remove, al_temp_cost, list;
    private ArrayList<Integer> al_new_temp = new ArrayList<>();
    private Node[] node;

    private void getShortestDistance(Node n) 
    {
        x = n.a;
        list = new ArrayList<>();
        list = n.al;
        temp_final_matrix = new int[no_of_cities][no_of_cities];
        al_remove = new ArrayList<>();
        n.setVisited(true);
        hm_visited.put(n.a, -1);
        System.out.println("Visited node "+hm_city.get(x));
        try
        {
            for(int b : list) 
            {
                if(final_matrix[start_city_id][b]>=(adj_matrix[x][b]+final_matrix[start_city_id][x]) && hm_visited.get(b)>0)
                {
                    final_matrix[start_city_id][b] = adj_matrix[x][b]+final_matrix[start_city_id][x];
                    al_new_temp.add(b);
                }
            }
        
            for(int i=0;i<no_of_cities;i++)
            {
                System.arraycopy(final_matrix[i], 0, temp_final_matrix[i], 0, no_of_cities);
            }
        
        
            //remove visited nodes from al_temp 
            for(int i : al_new_temp)
            {
                if(hm_visited.get(i)<0)
                {
                    al_remove.add(i);
                }
            }
            al_new_temp.removeAll(al_remove);

            //mechanism to sort al_temp according to its value in final_matrix
            al_temp_cost = new ArrayList<>();
            for(int i : al_new_temp)
            {
                al_temp_cost.add(final_matrix[start_city_id][i]);
            }
            al_new_temp.clear();
            Collections.sort(al_temp_cost);
            for(int i : al_temp_cost)
            {
                t=i;
                for(int j=0;j<no_of_cities;j++)
                {
                    if(t==temp_final_matrix[start_city_id][j] && hm_visited.get(j)>0)
                    {
                        al_new_temp.add(j);
                        t = -1;
                        temp_final_matrix[start_city_id][j] = -2;
                    }
                }
            
            }
        }
        catch(Exception e)
        {
            System.out.println(e);
        }
    }

    private static class Node 
    {
        private boolean visit;
        private final ArrayList al;
        private final int a;
        
        public Node(int a, ArrayList al, boolean t)
        {
            this.a = a;
            this.al = al;
            System.out.println("Connections for node "+a+" are : "+al);
            visit = t;
        }
        
        //set the node as visited
        public void setVisited(boolean t)
        {
            visit = t;
        }
        
        //check if the node is visited or not
        public boolean isVisited()
        {
            return visit;
        }
    }

    void ShortestDistance(String input1, int input2, String input3, String input4) 
    {
        delims = "[{,}]+";
        delim = "[{(,)}]+";
        cities = input1;
        set_of_roads = input2;
        toll_table = input3;
        min_toll = input4;
        max_value = 100;
        
        //Split the cities part in an arraylist or input1
        al_cities = new ArrayList<>(Arrays.asList(cities.split(delims)));
        al_cities.remove(0);
        no_of_cities = al_cities.size();
        
        
        
        //Assign a unique digit to each city starting frm 0 with city name as key
        HashMap<String, Integer> hm_cityid = new HashMap<>();
        for(int i=0;i<no_of_cities;i++)
        {
            hm_cityid.put(al_cities.get(i),i);
            
        }
        System.out.println(hm_cityid);
        
        //Assign a unique no a city name opposite of above
        hm_city = new HashMap<>();
        for(int i=0;i<no_of_cities;i++)
        {
            hm_city.put(i,al_cities.get(i));
        }
        System.out.println(hm_city);
        
        //to check if a city has been visited or not
        hm_visited = new HashMap<>();
        for(int i=0;i<no_of_cities;i++)
        {
            hm_visited.put(i, 1);
        }
        System.out.println(hm_visited);
        
        //ArrayList to store required dist road
        al_tk_min_toll = new ArrayList<>(Arrays.asList(min_toll.split(delims)));
        al_tk_min_toll.remove(0);
        
        //ArrayList to store parsed set of roads string
        al_tk_toll_table = new ArrayList<>(Arrays.asList(toll_table.split(delim)));
        al_tk_toll_table.remove(0);
        
        //store the toll tax table in 3 separate arraylist
        al_start_city = new ArrayList<>();
        al_end_city = new ArrayList<>();
        al_toll = new ArrayList<>();
        for(int i=0; i<set_of_roads; i++)
        {
            al_start_city.add(al_tk_toll_table.get(i*3));
            al_end_city.add(al_tk_toll_table.get((i*3)+1));
            al_toll.add(Integer.parseInt(al_tk_toll_table.get((i*3)+2)));
        }
        
        for(int i = 0; i<set_of_roads;i++)
        {
            System.out.println("start city : "+al_start_city.get(i)+", end city : "+al_end_city.get(i)+", table toll : "+al_toll.get(i));  
        }
        
        String[] tk_min_toll = min_toll.split(delims);
        start_city = tk_min_toll[1];
        end_city = tk_min_toll[2];
        start_city_id = hm_cityid.get(start_city);
        end_city_id = hm_cityid.get(end_city);
        
        //create an adjacency and final matrix for the toll table
        adj_matrix = new int[no_of_cities][no_of_cities];
        temp_adj_matrix = new int[no_of_cities][no_of_cities];
        final_matrix = new int[no_of_cities][no_of_cities];
        for(int i=0;i<no_of_cities;i++)
        {
            for(int j=0;j<no_of_cities;j++)
            {        
                if(i==j)
                {
                    adj_matrix[i][j] = 0;
                    final_matrix[i][j] = 0;
                }
                else
                {
                    adj_matrix[i][j] = max_value;
                    final_matrix[i][j] = max_value;
                }
                
            }
        }
        
        //fill the matrix considering an undirected graph
        for(int k=0;k<set_of_roads;k++)
        {
            temp_start_city = hm_cityid.get(al_start_city.get(k));
            temp_end_city = hm_cityid.get(al_end_city.get(k));
            temp_road_toll = al_toll.get(k);        
            adj_matrix[temp_start_city][temp_end_city] = temp_road_toll;
            adj_matrix[temp_end_city][temp_start_city] = temp_road_toll;
        }
        
        //print the adjacency matrix
        System.out.println("\t\tAdjacency Matrix");
        for(int i=0;i<no_of_cities;i++)
        {
            for(int j=0;j<no_of_cities;j++)
            {
                System.out.print(adj_matrix[i][j]+"\t");
            }
            System.out.println();
        }
        
        
        //declare array for node objects
        node = new Node[no_of_cities];
        
        //mechanism to create node objects to store info like current node and 
        //its connections in order of its cost
        for(int i=0;i<no_of_cities;i++)
        {
            System.arraycopy(adj_matrix[i], 0, temp_adj_matrix[i], 0, no_of_cities);
        }
        
        
        for(int i=0;i<no_of_cities;i++)
        {
            al_next = new ArrayList<>();
            al_cost = new ArrayList<>();
            for(int j=0;j<no_of_cities;j++)
            {
                if(adj_matrix[i][j]<max_value && adj_matrix[i][j]!=0 )
                {
                    al_cost.add(adj_matrix[i][j]);
                }
            }
            Collections.sort(al_cost);
            for(int m : al_cost)
            {
                t = m;
                for(int k=0;k<no_of_cities;k++)
                {
                    if(t==temp_adj_matrix[i][k])
                    {
                        al_next.add(k);
                        t = -1;
                        temp_adj_matrix[i][k] = -2;
                    }
                }
                
            }
//            System.out.println("Connections from Node "+i+" are : "+al_next);
            node[i] = new Node(i, al_next, false);
        }
        
        //print the adjacency matrix
        System.out.println("\t\tAdjacency Matrix");
        for(int i=0;i<no_of_cities;i++)
        {
            for(int j=0;j<no_of_cities;j++)
            {
                System.out.print(adj_matrix[i][j]+"\t");
            }
            System.out.println();
        }
        
        //mechanism to find shortest distance
        temp_start = start_city_id;
        for(int i=0;i<no_of_cities;i++)
        {
            if(node[i].a==start_city_id && !node[i].isVisited())
            {
                getShortestDistance(node[i]);
            }
        }
        
        while(hm_visited.containsValue(1))
        {
            al_temp = new ArrayList<>();
            al_temp.addAll(al_new_temp);
//            al_temp = al_new_temp;
              int q = al_temp.get(0);
                for(int j=0;j<no_of_cities;j++)
                {
                    if(node[j].a==q)
                    {
                        getShortestDistance(node[j]);
                    }
                }  
        }

        //print the final matrix
        System.out.println("\t\tFinal Matrix");
        for(int i=0;i<no_of_cities;i++)
        {
            for(int j=0;j<no_of_cities;j++)
            {
                System.out.print(final_matrix[i][j]+"\t");
            }
            System.out.println();
        }
        
        output1 = final_matrix[start_city_id][end_city_id];
        System.out.println("\nShortest distance between "+start_city+" and "+end_city+" is "+output1);
    }
    
}